package hot100;

public class Solution41 {
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int index = nums[i] - 1;
            while (index >= 0 && index < nums.length) {
                if (nums[index] == nums[i]) {
                    break;
                }
                int tmp = nums[index];
                nums[index] = nums[i];
                nums[i] = tmp;
                index = nums[i] - 1;
            }
        }
        int i = 0;
        while (i < nums.length) {
            if (nums[i] != i + 1) {
                break;
            }
            i++;
        }
        return i + 1;
    }

    public static void main(String[] args) {
        Solution41 solution41 = new Solution41();
        System.out.println(solution41.firstMissingPositive(new int[]{3, 4, -1, 1}));
    }
}
